#include "dlist.h"

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

void dlist_init (st_dlist_head *dlist)
{
    dlist -> size = 0;
    dlist -> head = NULL;
    dlist -> tail = NULL;
    return;
}

void dlist_destroy(st_dlist_head *dlist)
{
    st_dlist_node *p_node = NULL;
    
    while (dlist ->  size > 0) {
        p_node = dlist->head;
        dlist->head = dlist->head->next;
        free(p_node);
        dlist->size--;
    }
    memset(dlist, 0 , sizeof(st_dlist_head));
    return;
}

int dlist_insert_head(st_dlist_head *dlist, st_dlist_node *p_node, int data)
{
    if (dlist == NULL) return -1;
    if (p_node == NULL) {
        p_node = (st_dlist_node*)malloc(sizeof(st_dlist_node));
        if (p_node == NULL) return -2;
    }

    p_node->data = data;
    p_node->next = NULL;
    p_node->prev = NULL;

    if (dlist->size == 0) {
        dlist->head = p_node;
        dlist->tail = p_node;
    } else {
        p_node->next = dlist->head;
        p_node->prev = dlist->head->prev;
        dlist->head->prev = p_node;
        dlist->head = p_node;
    }

    dlist->size++;
    return 0;
}

st_dlist_node * dlist_remove_tail(st_dlist_head *dlist)
{
    st_dlist_node *p_node = NULL;
    if(dlist->size == 0) return NULL;
    
    p_node = dlist->tail;
    if (dlist->size == 1) {
        dlist->head = NULL;
        dlist->tail = NULL;
        dlist->size--;
        return p_node;

    } else {
        dlist->tail = dlist->tail->prev;
        dlist->tail->next = NULL; // tail 指针已经指向第二个了
    }
    dlist->size--;
    return p_node;
}

void dlist_remove_node(st_dlist_head *dlist, st_dlist_node *p_node)
{
    if (dlist->head == NULL || p_node == NULL) return;

    if (dlist->head == p_node) {
        dlist->head = p_node->next;
        dlist->head->prev = NULL;

    } else if (dlist->tail == p_node) {
        dlist->tail = p_node->prev;
        dlist->tail->next = NULL;
    } else {
        p_node->prev->next = p_node->next;
        p_node->next->prev = p_node->prev;
    }

    dlist->size --;
    p_node->next = NULL;
    p_node->prev = NULL;
    free(p_node);

    if (dlist->size == 0) memset(dlist, 0 , sizeof(st_dlist_head));
}

st_dlist_node *dlist_search (st_dlist_head *dlist, int data)
{
    if (dlist->head == NULL) return NULL;
    st_dlist_node *p_node = dlist->head;

    while (p_node != NULL) {  //注意不能错过最后一个
        if (p_node->data == data) return p_node;
        p_node = p_node->next;
    }

    return NULL;
}

void dlist_dump(st_dlist_head *dlist)
{
    int no = 0;
    st_dlist_node *p_node = dlist->head;
    while (p_node != NULL) {
        printf("\r\n [%d] = %d", no++, p_node->data);
        p_node = p_node->next;
    }

    return;
}

void lru_dlist(st_dlist_head *dlist, int data)
{
    st_dlist_node *p_node = NULL;

    p_node = dlist_search(dlist, data);
    if (p_node != NULL) {
        dlist_remove_node(dlist, p_node);
    } else if ( dlist->size >= 4) {
        p_node = dlist_remove_tail(dlist);
    }
    dlist_insert_head(dlist, p_node, data);

    return;
}

int main(void)
{
    st_dlist_head dlist = {0};
    st_dlist_node *p_node = NULL;
    dlist_init(&dlist);
    
       printf("\r\n inset 1,2,3");
    dlist_insert_head(&dlist,NULL,1);
    dlist_insert_head(&dlist,NULL,2);
    dlist_insert_head(&dlist,NULL,3); 

    dlist_dump(&dlist);

    p_node = dlist_remove_tail(&dlist);

   if(p_node != NULL) {
        printf("\r\n remove %d",p_node->data);
    }

    dlist_insert_head(&dlist,p_node,4);
    dlist_dump(&dlist);

    lru_dlist(&dlist,5);
    dlist_dump(&dlist);

    lru_dlist(&dlist,6);
    dlist_dump(&dlist);

    lru_dlist(&dlist,7);
    dlist_dump(&dlist);
    lru_dlist(&dlist,5);
    dlist_dump(&dlist);

    while(dlist.size > 0)
    {
        p_node = dlist_remove_tail(&dlist);
        if(p_node != NULL)
        { 
            printf("\r\n remove %d",p_node->data);
            free (p_node);
        }
    }    

    return 0;
}

